package graph;

import java.util.Arrays;

/**
 * 基于邻接矩阵的无向图
 */
public class MGraph {
    /**
     * 顶点数
     */
    private final int V;
    /**
     * 边数
     */
    private int E;
    /**
     * 邻接矩阵
     */
    private int[][] matrix;

    /**
     * 构造函数
     * 
     * @param V 顶点数
     */
    public MGraph(int V) {
        this.V = V;
        this.matrix = new int[V][V];
    }

    /**
     * 增加边，连接v和w
     * 
     * @param v
     * @param w
     */
    public void addEdge(int v, int w) {
        if (validateV(v) && validateV(w)) {
            matrix[v - 1][w - 1] = 1;
            matrix[w - 1][v - 1] = 1;
            E++;
        }
    }

    /**
     * 获取顶点数
     */
    public int V() {
        return V;
    }

    /**
     * 获取边数
     * 
     * @return
     */
    public int E() {
        return E;
    }

    @Override
    public String toString() {
        return Arrays.deepToString(matrix);
    }

    /**
     * 获取v的所有邻接点
     * 
     * @param v
     * @return v的所有邻节点
     */
    public int[] adj(int v) {
        if (validateV(v)){
            int[] returnValue = new int[V];
            int j = 0;
            for (int i = 0; i < matrix[v - 1].length; i++) {
                if (matrix[v - 1][i] > 0) {
                    returnValue[j] = i+1;
                    j++;
                }
            }
            int[] copyOfReturnValue = new int[j];
            for (int i = 0; i < copyOfReturnValue.length; i++){
                copyOfReturnValue[i] = returnValue[i];
            }
            return copyOfReturnValue;
        }else{
            return null;
        }

    }

    /**
     * 获取节点v的度
     * 
     * @param v
     * @return
     */
    public int getDegree(int v) {
        if (validateV(v)){
            return adj(v).length;
        }else{
            return 0;
        }
    }

    public boolean validateV(int v) {
        if (v < 1 || v > V) {
            System.out.println("请输入在1到" + V + "之间的顶点");
            return false;
        } else {
            return true;
        }
    }
}